/***************************************************************************\
 * The Mattise Kernel														*
 * Copyright 2007 Matthew Iselin											*
 * Licensed under the GPL													*
 *																			*
 * LinkedList.hpp															*
 *																			*
 * Easy-to-use linked list class for any type.								*
 *																			*
\***************************************************************************/

//--------------- Includes ---------------//
#include <iostream>
#include <stdio.h>
#include <memory.h>

//--------------- Class Definition ---------------//

/**
	The CLinkedList class basically is a shell around a certain data
	type. It allows linked lists to be created for any data type,
	hence saving coding time.
**/

// main class
template< class _T > class CLinkedList
{
	public:

		// initializes the list
		CLinkedList();

		// destroys all data in the list
		~CLinkedList();

		// dumps the list
		void Dump();

		// clears the list
		void Clear();

		// inserts data at the given offset, shifting everything else
		int Insert( _T, int );

		// pushes data onto the end of the list
		int Push( _T );

		// pops data off the end of the list
		_T Pop();

		// gets data from the list
		_T Get( int );

		// deletes an item
		void Delete( int );
		
		// retrieves the size
		int Size();

	private:

		// the list type
		struct myType
		{
			_T data;
			struct myType* next;
			struct myType* prev;
		};

		// the start of the list
		struct myType start;
		
		// size of the list
		int size;
};

template< class _T > CLinkedList<_T>::CLinkedList()
{
	// set the next and prev fields of start to null
	start.next = start.prev = (struct myType*) NULL;
	
	// there are no elements yet
	size = 0;
}

template< class _T > CLinkedList<_T>::~CLinkedList()
{
	// clear the list, free the memory
	Clear();
}

template< class _T > int CLinkedList<_T>::Size()
{
	// return the size
	return size;
}

template< class _T > void CLinkedList<_T>::Dump()
{
	// iterate through the list, displaying information about each item

	// running pointer
	struct myType* curr = start.next;

	// running accumulator
	unsigned int i = 0;

	// delete each item
	while( curr != (struct myType*) NULL )
	{
		// print it
		cout << "LIST[" << i++ << "]: " << curr->data << endl;

		// get the next pointer
		curr = curr->next;
	}
}

template< class _T > int CLinkedList<_T>::Push( _T d )
{
	// find the end of the list, then append the data

	// running pointers
	struct myType* prev, *curr = &start;

	// wait until curr is null
	while( curr != (struct myType*) NULL )
	{
		// save the current pointer
		prev = curr;

		// load the next one
		curr = curr->next;
	}

	// check that the one we want to add to isn't null
	if( prev == (struct myType*) NULL )
	{
		// fail!
		return -1;
	}

	// safe, so append - we need to make a structure first
	struct myType* m = (struct myType*) kmalloc( sizeof( struct myType ) );
	m->prev = prev;
	m->next = (struct myType*) NULL;
	m->data = d;

	// fill it in
	prev->next = m;
	
	// one more element
	size++;

	// success!
	return size-1;
}

template< class _T > _T CLinkedList<_T>::Pop()
{
	// find the end of the list, and remove it after saving its data

	// running pointers
	struct myType* prev, *curr = &start;

	// wait until curr is null
	while( curr != (struct myType*) NULL )
	{
		// save the current pointer
		prev = curr;

		// load the next one
		curr = curr->next;
	}

	// check that prev isn't null
	if( prev == (struct myType*) NULL )
	{
		// return start's data
		return start.data;
	}

	// prev holds the data we want
	_T ret = prev->data;

	// now unlink prev (the previous one's next is NULL)
	prev->prev->next = (struct myType*) NULL;

	// and free the pointer
	kfree( prev );
	
	// one less element
	size--;

	// return the data
	return ret;
}

template< class _T > _T CLinkedList<_T>::Get( int offset )
{
	// loop through the list until we hit either NULL or the offset

	// offset into the list
	int o = 0;

	// running pointer
	struct myType* curr = start.next;

	// keep on going
	while( o++ != offset && curr != (struct myType*) NULL )
		curr = curr->next;

	// we've hit the offset or NULL
	if( curr == (struct myType*) NULL )
		return start.data;

	// return the data
	return curr->data;
}

template< class _T > void CLinkedList<_T>::Delete( int offset )
{
	// loop through the list until we hit either NULL or the offset
	// then unlink it

	// offset into the list
	int o = 0;

	// running pointer
	struct myType* curr = start.next;

	// keep on going
	while( o++ != offset && curr != (struct myType*) NULL )
		curr = curr->next;

	// we've hit the offset or NULL
	if( curr == (struct myType*) NULL )
		return;

	// unlink the item
	if( curr->prev )
		curr->prev->next = curr->next;
	if( curr->next )
		curr->next->prev = curr->prev;
	
	// one less element
	size--;

	// free the memory
	kfree( curr );
}

template< class _T > int CLinkedList<_T>::Insert( _T d, int offset )
{
	// loop through the list until we hit either NULL or the offset
	// then append data to it

	// offset into the list
	int o = 0;

	// running pointer
	struct myType* curr = start.next;

	// keep on going
	while( o++ != offset && curr != (struct myType*) NULL )
		curr = curr->next;

	// we've hit the offset or NULL
	if( curr == (struct myType*) NULL )
		return -1;

	// create a new item
	struct myType* m = (struct myType*) kmalloc( sizeof( struct myType ) );
	m->data = d;
	m->next = curr->next;
	m->prev = curr;

	// link it into the list
	curr->next = m;
	
	// one more element
	size++;

	// success!
	return 0;
}

template< class _T > void CLinkedList<_T>::Clear()
{
	// iterate through the list, freeing memory as we go

	// running pointers - never start at 'start' because it isn't heap allocated
	struct myType* savnext, *curr = start.next;

	// delete each item
	while( curr != (struct myType*) NULL )
	{
		// save this one's next
		savnext = curr->next;

		// delete this one
		kfree( curr );

		// get the next pointer
		curr = savnext;
	}

	// and make sure start is setup properly
	start.next = (struct myType*) NULL;
	start.prev = (struct myType*) NULL;
	
	// there are no elements
	size = 0;
}
